"""
有一个无序整型数组，如何求出该数组排序后的任意两个相邻元素的最大差值？
    如：
        无序数组： 2  6  3  4  5  10  9
        排序结果： 2  3  4  5  6  9  10
        最大相邻差： 9 - 6 = 3

要求时间复杂度和空间复杂度尽可能低。
"""


def get_max_sorted_distance(array=None):
    if array is None:
        array = []
    new_array = []
    array = sorted(array)
    for i in range(len(array) - 1, -1, -1):
        if i - 1 >= 0:
            new_array.append(array[i] - array[i - 1])
    return max(new_array)


class Bucket:
    def __init__(self):
        self.max = None
        self.min = None


def get_max_sorted_distance_v2(array):
    """
    最优解
    计数排序和桶排序的思想
    :param array:
    :return:
    """
    # 1.得到数列的最大值和最小值
    max_value = array[0]
    min_value = array[0]
    for i in range(1, len(array)):
        if array[i] > max_value:
            max_value = array[i]
        if array[i] < min_value:
            min_value = array[i]
    d = max_value - min_value
    # 如果 max_value 和 min_value 相等，说明数组所偶元素都相等，返回 0
    if max_value == min_value:
        return 0

    # 2.初始化桶
    bucket_num = len(array)
    buckets = []
    for i in range(0, bucket_num):
        buckets.append(Bucket())

    # 3.遍历原始数组，确定每个桶的最大值和最小值
    for i in range(0, len(array)):
        # 确定数组元素所属的桶下标
        index = int((array[i] - min_value) * (bucket_num - 1) / d)
        if buckets[index].min is None or buckets[index].min > array[i]:
            buckets[index].min = array[i]
        if buckets[index].max is None or buckets[index].max < array[i]:
            buckets[index].max = array[i]

    # 4.遍历桶，找到最大差值
    left_max = buckets[0].max
    max_distance = 0
    for i in range(1, len(buckets)):
        if buckets[i].min is None:
            continue
        if buckets[i].min - left_max > max_distance:
            max_distance = buckets[i].min - left_max
        left_max = buckets[i].max
    return max_distance


print(get_max_sorted_distance([2, 6, 3, 4, 5, 10, 9]))
